#include <iostream>
#include <strings.h>
using namespace std;
// 28. 找出字符串中第一个匹配项的下标
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
// 如果 needle 不是 haystack 的一部分，则返回  -1 。

class Solution {
public:
    int strStr(string haystack, string needle) {
        return BF(haystack.c_str(), needle.c_str());
    }

private:
    int BF(const char* s, const char* t)
    {
        int n = strlen(s);
        int m = strlen(t);
        int i = 0, j = 0;
        while(i < n && j < m)   // 两个串都没有扫描完时循环
        {
            if(s[i] == t[j])    // 当前比较的字符相同
            {                   // 依次比较后续两个字符
                i++;
                j++;
            }
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }

        if(j >= m)          // j超界，表示t是s的子串
            return i-j;     // 返回t在s中的位置e
        else
            return -1;
    }
};
int main() {
    string haystack1 = "sadbutsad", needle1 = "sad";
    std::cout << Solution().strStr(haystack1, needle1) << std::endl;    // 0

    string haystack2 = "leetcode", needle2 = "leeto";
    std::cout << Solution().strStr(haystack2, needle2) << std::endl;    // -1

    string haystack3 = "hello", needle3 = "ll";
    std::cout << Solution().strStr(haystack3, needle3) << std::endl;    // 2
    return 0;
}
